package cn.foolishbird.crow.structure.linearlist;

import org.apache.commons.collections4.CollectionUtils;

import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;

/**
 * 链表工具类
 *
 * @author foolish bird
 * @email luohongtu@foolishbird.cn
 */
public final class LinearListUtils {

    private LinearListUtils() {

    }

    /**
     * 一些链表对象
     *
     * @param elements 一组元素
     * @param <E>      单链表泛型
     * @return 分层好的单链表
     */
    public static <E, ID, D  extends SinglyLinkedData<ID>> List<List<E>> hierarchy(List<D> elements,
                                                                             Function<D, E> apply) {
        if (CollectionUtils.isEmpty(elements)) {
            return Collections.emptyList();
        }
        // 找出顶层node
        Set<ID> ids = elements.stream()
                .map(SinglyLinkedData::id)
                .filter(Objects::nonNull)
                .collect(Collectors.toSet());

        Set<ID> nextIds = elements.stream()
                .map(SinglyLinkedData::nextId)
                .filter(Objects::nonNull)
                .collect(Collectors.toSet());

        Collection<ID> parentIds = CollectionUtils.subtract(ids, nextIds);
        if (CollectionUtils.isEmpty(parentIds)) {
            return Collections.emptyList();
        }

        Map<ID, D> nodeMap = elements.stream()
                .collect(Collectors.toMap(SinglyLinkedData::id, Function.identity(), (o, n) -> o));
        return parentIds.stream()
                .map(parentId -> {
                    List<E> list = new ArrayList<>();
                    D d = nodeMap.get(parentId);
                    list.add(apply.apply(d));
                    ID nextId = d.nextId();
                    while (Objects.nonNull(nextId) && Objects.nonNull(nodeMap.get(nextId))) {
                        D nextNode = nodeMap.get(nextId);
                        list.add(apply.apply(nextNode));
                        nextId = nextNode.nextId();
                    }
                    return list;
                }).collect(Collectors.toList());
    }


}
